(a) Field of the Invention
The present invention relates to the field of optical correlators which are used to recognize patterns in two dimensional images; more specifically, correlators which both recognize patterns at the image frame rate of the video images being examined, that is to say at a real-time rate, and which can have their reference image programmed, meaning updated or replaced, at video rates or even faster. Even more specifically, the present invention relates to correlators which can adaptively update their reference image, that is to say program themselves with new references at or near real-time, from recently observed video images. Typical video frame rates are 30 frames per second. The technologies of my invention are even capable of much faster image frame rates.
(b) Description of the Prior Art
The mathematical operation of correlation is widely applicable to the recognition of patterns (e.g. characters, faces, fingerprints, vehicles) in images and autonomous guidance of robotic systems by images. Many varied applications, including use in radar and communication systems, and parts inspection systems, have been taught in prior United States patents; such as, for example, U.S. Pat. No. 4,695,973 to Yu; U.S. Pat. No. 4,765,714 to Horner. See, also, K. H. Fielding, J. L. Horner and C. K. Makekau, "Optical fingerprint identification by binary transform correlation," Opt. Eng., 30, 12, 1958-61 (December, 1991). Potential future applications include use as part of optical neural network architectures and optical associative memories. Whether a correlator is used in these typically real-time systems often depends on the time required to perform the correlations.
The correlation integral can be calculated by digital computers, but when correlating long length signals, the number of computer operations can often take too much time. Fast correlation is often performed using the Fast Fourier Transform (FFT) algorithm on a computer. The number of operations for the FFT is known to be N log.sub.2 N complex adds and multiplies, where N is the number of points to be correlated. (In a video image this might be as large as 1000.times.1000 pixels or 1 million points.) One complex add and multiply is equivalent to 4 real adds and 4 real multiplies. Three FFTs are required to perform a correlation, so correlation requires 0.5 billion floating point operations. Recent Cray computers (circa 1991, 2 gigaflops) would be able to compute only 4 image correlations per second, would consume much energy, and are quite large and expensive. Furthermore, if customized programming is required for a specific application of correlation, then, substantial costs are frequently involved.
Specialized analog signal processors have been developed for real-time applications that are too taxing for digital computers. In addition to their equivalent computation rates, analog processors can be smaller, lighter and more energy efficient.
Optical correlators perform the equivalent of the mathematical operation of correlation between two images (or signals) in an analog fashion, based on the physical properties of optical waves and the response of photosensitive (or photodetecting) materials to optical waves. The operation of coherent optical correlators ("optical correlator") is based on the interference of nearly monochromatic optical waves (primarily lasers). Any optical correlator takes two images as input, one considered the object to be identified (template, reference image) the other being the image to be inspected (scene image, test image). The image at the output of the correlator (correlation plane) represents the correlation integral of the two images. If two images are similar in shape, size and variation in intensity, the input is transformed into a narrow, large intensity peak in the correlation plane. The location of the peak is exactly proportional to the lateral offset between the correlated objects in the two images. Typically, a video camera views and records the correlation plane. A computer or electronic system can then simply and quickly examine the correlation plane image on a pixel-by-pixel basis to determine if the intensity exceeds a threshold for positive identification, and if so, record the pixel location (locations) of the correlated object (objects).
The actual reference image (and in some variants the test image) is introduced into various correlators in different ways. In the case of the joint transform correlator (JTC), both images are placed side-by-side in an object (image) plane. This is to say that transparencies of the two images are illuminated by a uniform intensity plane wave, or in practice, by a collimated beam of laser light. See C. S. Weaver and J. W. Goodman, "A technique for optically convolving two functions," Appl. Opt. 5, 1248 (1966). In the Vander Lugt correlator (VLC), a complex-valued transmittance (reflectance), called a matched filter, is placed at the focal plane (Fourier plane, filter plane) of the correlator. The filter transmittance is proportional to the complex conjugate of the Fourier transform spectrum of the input image. See A. Vander Lugt, "Signal Detection by Complex Spatial Filtering," IEEE Trans. Information Theory, IT-10, 139-145, 1964. It is known that the complex wave amplitudes found at the focal plane, resulting from illuminating the input image, are well approximated by the Fourier spectrum of the image. See J. W. Goodman, Introduction to Fourier Optics, McGraw-Hill, 1968. The complex transmittance of the matched filter is generated by a holographic recording process. The nonlinear recording properties of photosensitive materials (e.g. square law) necessarily records other terms. Proper recording procedures enable the non-correlation part of the transmittance to reconstruct at an adequate distance from the center of the correlation plane, so that there is little interference from these terms. However, these other terms also reduce the amount of light that diffracts into correlation peaks, increase noise, reduce dynamic range of the correlator, and cause the holographic recording to have a higher spatial resolution (maximum number of resolvable pixels, space-bandwidth) than would otherwise be needed if the complex-valued matched filter alone was available. Designing arbitrary complex-valued filters without recording nonlinear terms has generally been considered to be impractical. Recent real-time complex valued filters are discussed below in the Background discussion of Spatial Light Modulators (SLMs). Detail on the theory and properties of the classical matched filter and the related correlation receiver is taught in P. LaFrance, Fundamental Concepts in Communication, Ch. 2, Prentice-Hall, Englewood Cliffs, N.J. (1990).
The JTC also uses a holographic recording procedure, but, in this case, the interference pattern of the complex spectra of scene and reference images expose the film at the focal plane of the correlator. Reconstruction of this hologram also contains a correlation plane, as well as other non-correlation terms, which degrade the correlation plane in similar manner as noted for the VLC.
In a phase-only correlator (POC), a phase-only filter replaces the matched filter of the Vander Lugt correlator. This filter is identical to the matched filter in phase but its magnitude is set to one. See J. L. Horner and P. D. Gianino, "Phase-only matched filtering," Appl. Opt., 23, 6, 812-16 (15 March, 1984). Computer designed phase-only filters have also been referred to as kinoforms. See L. B. Lessem, P. Hirsch, and J. A. Jordan, Jr., "The kinoform: a new wavefront reconstruction devices," IBM J. Res. Dev., 13, 1520 (1969). The phases for the phase-only filter are typically calculated from a FFT of the image, where the FFT (with an adequate number of samples) well approximates the Fourier transform relationship between the object and focal plane. Such filters are usually manufactured by forming a relief structure on a glass plate by photolithographic etching procedures, such as, for example, those procedures used in semiconductor processing. The manufacturing procedure is especially easy if only binary phases are implemented. These type of correlators are especially desirable, in that they can have 100% diffraction efficiency, as taught in J. L. Horner, "Light utilization in optical correlators," Appl. Opt., 21, 24, 4511-14, (Dec. 15, 1982). That is, all the light energy can be focused into a single intensity peak in the correlation plane. Phase-only filtering in the frequency plane of a correlator has the advantage in detecting objects over Vander Lugt correlation of narrower correlation peaks but a greater sensitivity to scale and rotation changes. See Horner U.S. Pat. No. 4,588,260.
A special case of the POC is the binary phase-only correlator (BPOC). See Horner U.S. Pat. No. 4,765,714. The filter in the BPOC differs from the POC in that phases of the POC closer to 0 than .pi. are mapped to 0, and phases closer to .pi. are mapped to .pi.. Deterministic simulations, see J. L. Horner and J. R. Leger, "Pattern recognition with binary phase-only filters," Applied Optics, 24, 5, 609-11 (Mar. 1, 1985); and analysis of phase truncation as a random process, see R. W. Cohn, "Random phase errors and pseudo-random modulation of deformable mirror spatial light modulators," Proc. SPIE V. 1772-34 (1992); both indicate that the BPOC is only 40% as efficient as the POC at directing light into the correlation plane While the BPOC is more efficient than the VLC and JTC, it is still less efficient than the POC. The increased levels of noise in the BPOC are also analyzed in R. W. Cohn.
In many systems, it is often necessary to perform correlation on each test image as it is presented to the system. Thus, for optical correlators to perform in real-time, it is necessary that each test image must be displayed on a spatial light modulator capable of real-time rates. An even more flexible correlator would allow one or more reference images to be compared against each test image. In this case, a real-time spatial light modulator is needed for the reference image as well, in which case the correlator is said to be programmable. The most flexible correlator is said to be "adaptive" if it is capable of being programmed with new reference images from recently observed images. Adaptive correlators are a special case of programmable correlators. Nonadaptive programmable correlators only use precalculated, prestored or prerecorded images to update the reference image.
There are specific optical correlator realizations that have demonstrated differing degrees of flexibility. As early as 1977, a VLC using a real-time SLM in the input plane and a permanently recorded hologram in the focal plane demonstrated real-time operation, though non-programmable and non-adaptive. See J. Upatnieks, "Portable real-time coherent optical correlator," Appl. Opt., 22, 18, 2798-2803 (Sep. 15, 1983) and references therein. Programmable and adaptive operation using rewrittable materials, e.g. thermoplastic films, photorefractive crystals and liquid crystal light valves, at the filter plane has more recently been taught. See U.S. Pat. No. 4,383,734. Recent JTCs have demonstrated adaptive real-time operation. Test and reference images are placed on adjacent halves of a single electrically-addressed SLM in the input plane. The intensity of the resulting Fourier plane image is recorded by a video camera. Photodetection of the resulting image is basically equivalent to the nonlinear detection process used for making holograms, though the cameras used usually have much lower resolution. The camera, as opposed to film, is a real-time device. Its signal is fed to a video-rate SLM, e.g. a liquid crystal display from a hand held television. The Fourier transform of this transmittance by a second lens system forms the desired correlation plane image. See Yu U.S. Pat. No. 4,695,973 and F.T.S. Yu, S. Jutamulia, T. W. Lin, D. A. Gregory, "Adaptive Real-Time Pattern Recognition Using a Liquid Crystal TV Based Joint Transform Correlator," Applied Optics, 26, 8, 1370-72 (Apr. 15, 1987).
The most flexible POC envisioned to date would use a real-time input plane SLM and a real-time phase-only SLM in the filter plane. It is programmed by selecting one of a set of images representing the phase at each individual pixel of the SLM in an electronic (or optical) memory. Adaptive operation of the POC is impractical if the phase weights are determined by FFT, because of the computation time of the FFT and because the optical correlator is being used to eliminate the need for digital computation of the FFT. Thus, while JTC offers small size and adaptivity, it suffers from poor utilization of light when compared with the POC. The POC, however, is not adaptive.
The good performance of phase-only filters and the prior lack of real-time, phase-only SLMs has led to recent approaches in which the filter plane of an optical correlator approximates the characteristics of the phase-only filter. Mathematical analyses show that for specific nonlinear mappings of detected filter plane intensities, specific terms of a harmonic expansion are equivalent to the phase of the phase-only matched filter. The other harmonic terms primarily reduce the energy diffracted into the phase-only correlation peak. Demonstrations of both the JTC and a more recent "phase-extraction" correlator achieved performance which, in principle, is equivalent to a POC. While each correlator is capable of real-time adaptive operation, similar to JTC and VDL, the other nonlinear harmonics reduce the amount of light used for correlation to a small fraction of the light available for a true POC. See B. Javidi, "Nonlinear joint power spectrum based optical correlation," Appl. Opt., 28, 12, 2358-66 (Jun. 15, 1989) and T. Kotzer, J. Rosen, and J. Shamir, "Phase extraction pattern recognition," Applied Optics, Vol. 31, 8, pp. 1126-1136 (Mar. 10, 1992).
Adaptive correlation has recently been demonstrated for the BPOC. See J. Knopp and S. E. Monroe, Jr., "Optical calculation of correlation filters," Proc. SPIE V. 1295, 68-75 (1990). The sign of the optical spectrum was determined from video images of the intensity of 1) the optical spectrum, 2) a reference beam, and 3) the interference pattern of the spectrum and reference beam. Mechanical shuttering is required to present each of the three images to the filter plane camera. A phase-only SLM in the filter plane is then programmed with either the value 0 or .pi. based on the measured sign. The authors mentioned that with the addition of a phase shifter and by recording a second interferogram, the determination of the phase would be possible, but that they were mainly interested in the small amount of computer calculations needed to decide on the sign.
Because of the low optical efficiency of the BPOC and the low fill factor of their spatial light modulator, decentering in the image plane (equivalent to tilt in the filter plane) was required to separate the correlation peak from the residual test image. In Kotzer et. al. tilt was used for the same reason, and in the JTC separation of reference from test image was used for this reason. In fact, the VLC was not the first approach that recorded complex weights; but by recording with a tilted reference it was for the first time possible to separate terms involved in correlation from those not involved. See Chapters 7 and 8 of Goodman.
Only today with the development of SLMs that can practically implement a full 2.pi. phase modulation is it practical to remove the restrictions of tilted recording wavefronts. Using full 2.pi. phase modulation, it now appears possible to direct all energy into correlation, which eliminates the need for a tilted reference; which has the addional advantage of not requiring as large optical apertures and, hence, lower cost optics.
Physically compact implementations are currently desired for many systems. Recent JTC demonstrations have achieved smaller size by using a single SLM, lens and video camera for both recording and reconstruction steps of the correlation process. This is often called "time-sharing of the optics." See Horner U.S. Pat. No. 5,040,140; K. H. Fielding and J. L. Horner, "1-f binary joint transform correlator," Opt. Eng., 29, 9, 1081-87 (Sep. 1990); and J. M. Florence, "Joint-transform correlator systems using deformable-mirror spatial light modulators," Opt. Lett., 14, 7, 341-43 (Apr. 1, 1989).
It is worth summarizing the basic similarities and distinctions between the various optical correlators described above. Each correlator by optical or optoelectronic means records phase of the Fourier spectrum of an image. Phase is usually recorded by holographic/interferometric techniques and reconstructed by holographic reconstruction or opto-electronic decoding and then programming of an SLM. One exception is using the FFT to electronically find the complex weights, but this is not practical for real-time adaptive correlators. The various techniques have demonstrated useful properties of real time operation, adaptivity, efficient use of light and compact size. None have achieved all these properties simulataneously.